#include <stdio.h>
#include <stdlib.h>

void merge(int *arr, int n, int range){
    // 如果范围大于数组长度，就不需要继续分割
    if(range>n){
        return;
    }

    int *temp_arr = (int*)malloc(n * sizeof(int));
    
    for(int i=0;i<n;i+=(2*range)){
        // 找到两组的范围
        int l = i, r = i+range;
        int _l = l+range, _r = r+range>n ? n : r+range; // 处理右侧越界

        // 如果右半部分的起始位置超出数组的范围，直接跳过
        if(r>n){
            continue;
        }
        int idx = i;
        while (l<_l && r<_r){
            if(arr[r]<arr[l]){
                temp_arr[idx] = arr[r];
                r++;
            }else{
                temp_arr[idx] = arr[l];
                l++;
            }
            idx++;
        }
        // 剩余部分合并
        while (l<_l)
        {
            temp_arr[idx] = arr[l];
            l++;
            idx++;
        }
        
        while (r<_r)
        {
            temp_arr[idx] = arr[r];
            r++;
            idx++;
        }
    }

    // 将临时数组复制回原数组
    for(int i=0;i<n;i++){
        arr[i] = temp_arr[i];
    }
    free(temp_arr);

    merge(arr,n,range*2);
}

int main(){
    int arr[] = {218,224,391,443,22,337,1125,49,506};
    int n = sizeof(arr)/sizeof(arr[0]);
    merge(arr,n,1);
    
    for(int i=0;i<n;i++){printf("%d ",arr[i]);}

    return 0;
}